Non-oblivious Local Search Heuristics for Traveling Salesman and Vehicle Routing Problems with Proved Performance Guarantees

Uri Yovel

Dep. of Statistics and Operations Research, School of Mathematical Sciences,

Tel-Aviv university

Abstract:

The traveling salesman problem (TSP) and the vehicle routing problem (VRP) are classical NP-hard problems in combinatorial optimization. The k-opt heuristics are among the most common techniques for approaching TSP. They are used either directly or as subroutines in more sophisticated heuristics, such as the celebrated Lin-Kernighan heuristic. The value of k is typically 2 or 3. In this paper, we modify the 2-opt heuristic to be based on a  function  f of the distances rather than the distances solely. This may be viewed as modifying the local search with the 2-change neighborhood to be non-oblivious. We denote the corresponding heuristic by (2,f)-opt. We provide theoretical performance guarantees for it: both lower and upper bounds based on the ones given by Chandra, Karloff, and Tovey (1999), obtained originally for the standard 2-opt heuristic; the upper bound is improved by a factor of √2 with respect to the known upper bound of the standard 2-opt. We then provide experimental evidence based on TSPLIB benchmark problems, showing that (2,f)-opt with  f(x) = x^r for various values of r < 1 significantly outperforms 2-opt.

We then briefly discuss a local search algorithm for the VRP; in particular, we show that the k-opt heuristic is not strong enough to guarantee a constant approximation ratio, and we present a different (non-oblivious) local search whose approximation ratio is 2. To the best of our knowledge, this is the first local search algorithm for this problem with proved performance guarantee.

Joint work with Asaf Levin.

ההרצאה תתקיים ביום שלישי, 08/01/13, בשעה 14:00 בחדר 206, בנין וולפסון הנדסה, הפקולטה להנדסה, אוניברסיטת תל-אביב